#include <bits/stdc++.h>
using namespace std;

/*
2302. 统计得分小于 K 的子数组数目
已解答
困难
相关标签
相关企业
提示
一个数组的 分数 定义为数组之和 乘以 数组的长度。

比方说，[1, 2, 3, 4, 5] 的分数为 (1 + 2 + 3 + 4 + 5) * 5 = 75 。
给你一个正整数数组 nums 和一个整数 k ，请你返回 nums 中分数 严格小于 k 的 非空整数子数组数目。

子数组 是数组中的一个连续元素序列。

 

示例 1：

输入：nums = [2,1,4,3,5], k = 10
输出：6
解释：
有 6 个子数组的分数小于 10 ：
- [2] 分数为 2 * 1 = 2 。
- [1] 分数为 1 * 1 = 1 。
- [4] 分数为 4 * 1 = 4 。
- [3] 分数为 3 * 1 = 3 。 
- [5] 分数为 5 * 1 = 5 。
- [2,1] 分数为 (2 + 1) * 2 = 6 。
注意，子数组 [1,4] 和 [4,3,5] 不符合要求，因为它们的分数分别为 10 和 36，但我们要求子数组的分数严格小于 10 。
示例 2：

输入：nums = [1,1,1], k = 5
输出：5
解释：
除了 [1,1,1] 以外每个子数组分数都小于 5 。
[1,1,1] 分数为 (1 + 1 + 1) * 3 = 9 ，大于 5 。
所以总共有 5 个子数组得分小于 5 。
 

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 105
1 <= k <= 1015
*/

// 法一
class Solution {
	public:
	using ll = long long;
	long long countSubarrays(vector<int>& nums, long long k) {
		// 滑动窗口
		ll ans = 0, sum = 0;
		int left = 0;
		for (int right = 0; right < nums.size(); ++right) {
			sum += nums[right];
			// 窗口收缩
			while (sum * (right - left + 1) >= k) {
				sum -= nums[left++];
			}
			// 累加右边框指针 以当前右指针结尾的所有合法子数组数目
			ans += right - left + 1;
		}
		return ans;
	}
};

// 法二
class Solution {
	public:
	long long countSubarrays(vector<int>& nums, long long k) {
		int n = nums.size();// 获取数组的长度
		long long ans = 0; // 用来存储符合条件的子数组数量        
		long long sum = 0;// 用来存储当前子数组的元素和
		// 初始化左右指针
		int left = 0;
		int right = 0;
		// 遍历数组，right指针用于扩展当前窗口
		while (right < nums.size()) {      
			sum += nums[right];    // 将当前右侧元素加入子数组
			++right;  // 移动右指针          
			// 如果当前子数组的分数 >= k，则通过移动左指针来缩小窗口
			while (left <= right && sum * (right - left) >= k) {              
				sum -= nums[left]; // 如果不符合条件，减去左端元素，并将左指针右移
				++left;
			}
			// 统计满足条件的子数组数量
			// 当前right位置的子数组，长度是从left到right的范围
			// 子数组的数量是right - left，因为子数组的长度可以是1到(right - left)
			ans += right - left;
		}
		
		// 返回符合条件的子数组数量
		return ans;
	}
};

// 法三
class Solution {
	public:
	long long countSubarrays(vector<int>& nums, long long k) {
		// 获取数组的长度
		int n = nums.size();	
		// 计算所有可能的子数组数量
		long long tot = 1ll * n * (n + 1) / 2;	
		// 用于存储窗口的当前和、分数、符合条件的子数组数量
		long long win_sum = 0, win_score = 0, ans = 0;
		// 使用双指针方式：l为左指针，r为右指针
		// 初始化左指针l为0，右指针r为-1
		for(int l = 0, r = -1; l < n && r < n;) {
			// 当前窗口的分数小于k，继续扩展窗口
			while(win_score < k){
				r++;  // 右指针向右移动
				if(r >= n) break;  // 如果右指针越界，退出
				// 计算窗口分数：
				// 当前窗口的分数为窗口长度 * 当前元素 + 当前窗口之前的和
				win_score += 1ll * (r - l + 1) * nums[r] + win_sum;
				win_sum += nums[r];  // 更新窗口的和
			}
			// 移动左指针，尝试缩小窗口
			l++;  
			// 更新窗口的分数，去掉左指针移动的元素的贡献
			win_score -= 1ll * (1ll * nums[l - 1] * (r - l + 2) + win_sum - nums[l - 1]);
			win_sum -= nums[l - 1];  // 去掉左指针元素的和

			// 统计符合条件的子数组数量
			ans += n - r;  // r指针到数组末尾的所有子数组都符合条件
		}
		// 返回所有子数组数量减去不符合条件的子数组数量
		return tot - ans;
	}
};

	